<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 树的节点
        function Node(value) {
            this.value = value
            this.left = null
            this.right = null
        }
        // 广度优先遍历
        function BFS(root) {
            if (root === null) return
            const queue = [root]
            while (queue.length) {
                const item = queue.shift()
                console.log(item.value)
                if (item.left) queue.push(item.left)
                if (item.right) queue.push(item.right)
            }
        }

        // 深度优先遍历-前序遍历
        function preDFS(root) {
            if (root === null) return
            console.log(root.value)
            if (root.left) preDFS(root.left)
            if (root.right) preDFS(root.right)
        }

        // 迭代前序遍历
        function iPreDFS(root) {
            if (root === null) return
            const stack = [root]
            while (stack.length) {
                const item = stack.pop()
                console.log(item)
                if (item.right) stack.push(item.right)
                if (item.left) stack.push(item.left)
            }
        }

        // 中序遍历
        function inDFS(root) {
            if (root === null) return
            if (root.left) inDFS(root.left)
            console.log(root.value)
            if (root.right) inDFS(root.right)
        }

        // 迭代中序遍历
        function iInDFS(root) {
            if (root === null) return
            const stack = []
            const curr = root
            while (stack.length || curr) {
                while (curr) {
                    stack.push(curr)
                    curr = curr.left
                }
                const leftMost = stack.pop()
                console.log(leftMost)
                curr = leftMost.right
            }
        }

        // 后序遍历
        function postDFS(root) {
            if (root === null) return
            if (root.left) postDFS(root.left)
            if (root.right) postDFS(root.right)
            console.log(root)
        }

        // 迭代后序遍历
        function iPostDFS(root) {
            if (root === null) []
            const tempStack = [root], result = []
            while (tempStack.length) {
                const last = tempStack.pop()
                result.push(last)
                if (last.left) tempStack.push(last.left)
                if (last.right) tempStack.push(last.right)
            }
            return result.reverse()
        }

        function iPostDFS2(root) {
            if (root === null) return
            const stack = []
            const stack2 = []
            const curr = root
            while (stack.length || curr) {
                while (curr) {
                    stack2.push(curr)
                    stack.push(curr)
                    curr = curr.right
                }
                if (stack.length) {
                    curr = stack.pop()
                    curr = curr.left
                }
            }
            while (stack2.length) {
                console.log(stack2.pop())
            }
        }

        function iPostDFS3(root) {
            if (root === null) return
            const stack = []
            const curr = root
            const pre = null
            while (stack.length || curr) {
                while (curr) {
                    stack.push(curr)
                    curr = curr.left
                }
                if (stack.length) {
                    curr = stack.pop()
                    if (curr.right === null || pre === curr.right) {
                        console.log(curr)
                        pre = curr
                        curr = null
                    } else {
                        stack.push(curr)
                        curr = curr.right
                    }
                }
            }
        }

        function* walkPreOrder(root) {
            if (root === null) return
            const stack = [root]
            while (stack.length) {
                const item = stack.pop()
                yield item
                if (item.right) stack.push(item.right)
                if (item.left) stack.push(item.left)
            }

        }

        const root = new Node(2)
        root.left = new Node(1)
        root.right = new Node(3)

        preDFS(root)

    </script>
</body>

</html>